/*

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
*/
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int x_len=board.size();
        int y_len=board[0].size();
        vector<vector<bool>> visited(x_len,vector<bool>(y_len,false));
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<board[i][j]<<" "; 
            }
            cout<<endl;
        }
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(dfs(visited,board,i,j,word,0)){
                    return true;
                }
            }
        }
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<visited[i][j]<<" ";
            }
            cout<<endl;
        }
        return false;
    }

private:
    vector<vector<int>> direction{{1,0},{-1,0},{0,1},{0,-1}};
    bool dfs(vector<vector<bool>>& v,vector<vector<char>>& b,int i,int j,string& s,int idx){
        if(idx==s.size()){
            return true;
        }
        if(0<=i&&i<b.size()&&0<=j&&j<b[0].size()&&!v[i][j]&&b[i][j]==s[idx]){
            for(auto& dir:direction){
                cout<<endl;
                for(int i=0;i<b.size();i++){
                    for(int j=0;j<b[0].size();j++){
                        cout<<v[i][j]<<" ";
                    }
                    cout<<endl;
                }

                v[i][j]=true;
                if(dfs(v,b,i+dir[0],j+dir[1],s,idx+1)){
                    v[i][j]=false;
                    return true;
                }
                v[i][j]=false;
            }
        }
        return false;
    }
};


int main(){
    Solution s;
    //vector<vector<char>> board{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    //string word="ABCCED";
    vector<vector<char>> board{{'a'}};
    string word="ab";
    cout<<endl;
    cout<<s.exist(board,word)<<endl;
    return 0;
}